
/**


 * Copyright (c) 2010,  Joel Andersson, Olle Br�nnlund, Hannes Gustafsson All rights reserved.

 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:

 *          - Redistributions of source code must retain the above copyright
 *          notice, this list of conditions and the following disclaimer.
 *          - Redistributions in binary form must reproduce the above copyright
 *          notice, this list of conditions and the following disclaimer in the
 *          documentation and/or other materials provided with the
 *          distribution.
 *          - Neither the name of the owner nor the names of its contributors
 *          may be used to endorse or promote products derived from this
 *          software without specific prior written permission.

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
import java.util.Arrays;
import java.util.BitSet;
import java.util.Random;

public class Main {

    static final int numPts = 1300;
    static final int numRectangles = 27;
    static int seed = 1; /* if seed = 0 we use a random seed */

    static final int x = 1000, y = 1000; /* size of our container */

    static final boolean onlyMER = true; /* only maximal empty rectangles*/

    static final int minimumArea = 0;
    static final int bitSetmatrixSize = 300; /* if 0 EmptyRectangleContainer is executed in standard. */


    public static void main(String[] args) {
        standard();
//        comparisonUsingBitSets(10);
    }

    /* Compare the result from all rectangles and MER.*/
    static public void allComparedToMaximal(int threshold) {
        Random rnd = new Random();
        EmptyRectangleContainer containerOnlyEMR, containerAllRect;
        while (true) {
            seed = rnd.nextInt();
            containerOnlyEMR = new EmptyRectangleContainer(x, y, numPts, seed, true, minimumArea);

            /* use branch-and-bound to select only valid candidates */
            containerOnlyEMR.branchAndBound(numRectangles, 0, new int[0], 0);
            /* generate a container  */
            containerAllRect = new EmptyRectangleContainer(x, y, numPts, seed, false, minimumArea);

            containerAllRect.branchAndBound(numRectangles, 0, new int[0], 0);
            if (containerAllRect.getMax() - containerOnlyEMR.getMax() > threshold) {
                System.out.format("Skillnad: %10d%n", (containerAllRect.getMax() - containerOnlyEMR.getMax()));
                break;
            }

        }

        new RectangleSpace("containerOnlyEMR", x, y, containerOnlyEMR.getPts(), containerOnlyEMR.getBestSolAsList());
        new RectangleSpace("containerAllRect", x, y, containerAllRect.getPts(), containerAllRect.getBestSolAsList());


    }

    static public void comparisonUsingBitSets(int iterations) {
        EmptyRectangleContainer withoutBitSets;
        ERContainerWithBitSets withBitSets;
        long total1 = 0, total2 = 0;
        long start1, start2, end1, end2;
        Random rnd = new Random();
        while (iterations > 0) {
            seed = rnd.nextInt();
            withoutBitSets = new EmptyRectangleContainer(x, y, numPts, seed, onlyMER, minimumArea);
            withBitSets = new ERContainerWithBitSets(x, y, numPts, seed, onlyMER, minimumArea);
            start1 = System.currentTimeMillis();
            withoutBitSets.branchAndBound(numRectangles, 0, new int[0], 0);
            end1 = System.currentTimeMillis();
            total1 += (end1 - start1);

            start2 = System.currentTimeMillis();
            withBitSets.branchAndBound(numRectangles, bitSetmatrixSize);
            end2 = System.currentTimeMillis();
            total2 += (end2 - start2);
            iterations--;
            if (withoutBitSets.max != withBitSets.max) {
                System.out.println("Buggs!");
                break;
            }
        }
        System.out.format("Execution time sliced off: %10.2f %%%n", ((1d - ((double) total2) / total1)) * 100d);

    }

    public static void standard() {
        EmptyRectangleContainer erc;
        long start = System.currentTimeMillis();
        if (bitSetmatrixSize > 0) {
            erc = new ERContainerWithBitSets(x, y, numPts, seed, onlyMER, minimumArea);
            ((ERContainerWithBitSets) erc).branchAndBound(numRectangles, bitSetmatrixSize);
            BitSet[] bs = ((ERContainerWithBitSets) erc).intersGraph;
            for (int i = 0; i < bs.length; i++) {
                System.out.print("Rectangle " + i + " cardinality is " + bs[i].cardinality() + " : ");
                System.out.println(bs[i].toString());
            }
        } else {
            erc = new EmptyRectangleContainer(x, y, numPts, seed, onlyMER, minimumArea);
            erc.branchAndBound(numRectangles, 0, new int[0], 0);
        }
        long end = System.currentTimeMillis();


        System.out.format("Execution time of branch-and-bound was %21s ms\n" +
                "Number of branch-and-bound calls: %26s\n" +
                "Best solution: %45s\n" +
                "Total area of solution: %36s au\n" +
                "Numbers of rectangles considered: %26s\n", (end - start), erc.getCalls(),
                Arrays.toString(erc.getBestSolAsInts()),
                erc.getMax(), erc.getIndexSmallestRec());

        /* show a graphical representation of all rectangles and of the rectangles in the solution */
//                new RectangleSpace("All", x, y, erc.getPts(), erc.getRectangleList());
//                new RectangleSpace("Chosen", x, y, erc.getPts(), erc.getBestSolAsList());

    }
}
